Computerized devices control almost every aspect of our life—from writing documents to controlling traffic lights. However, computerized systems are bug-prone, and thus require a testing phase in which the bugs should be discovered. The testing phase is considered one of the most difficult tasks in designing a computerized device. The cost of not discovering a bug may be enormous, as the consequences of the bug may be disastrous. For example, a bug may cause the injury of a person relying on the designated behavior of the computerized system. Additionally, a bug in hardware or firmware of a marketed product may be expensive to fix, as patching it requires call-back of the computerized device. Hence, many developers of computerized systems invest a substantial portion of the development cycle to discover erroneous behaviors of the computerized device.
An important part of testing relates to test planning and design, i.e., providing a set of tests that adequately cover the system, such that if all tests pass the system is assumed to be operative. However, it is generally required to increase testing efficiency and reduce the number or total cost of the tests as much as possible.
A common methodology for test planning and design comprises the usage of combinatorial models, also referred to as Cartesian-product models, which may be used when describing a problem as a set of attributes or properties, values corresponding to the attributes, and restrictions on values or combinations of values that may not appear together in a test. Each test comprises a value for each attribute, such that the combination represents a particular situation. Thus, a test may be represented as a tuple in which every attribute is assigned a value. The model thus spans a space of valid tests, being the value assignments that do not violate any restrictions.
Combinatorial models may have several usages, one of which may be as the input to Combinatorial Test Design (CTD), a test planning technique that selects a subset of the valid test space which covers all interactions up to a certain level, which may be user-defined. Another important usage is for analysis of functional coverage of systems.
One obstacle of CTD deployment lies in correctly capturing the restrictions. Under-restricting the model yields impossible tests, i.e., tests that cannot be executed, and eventually coverage gaps may occur if these tests are skipped or manually modified. Over-restricting, on the other hand, also yields coverage gaps in areas that are wrongfully restricted.